package com.demo.java.alg;

public class SimString {

    // 负债表+滑动窗口解决
    public static int simstr(String str, String sim) {
        int invalids = 0;
        char[] sims = sim.toCharArray();
        int[] init = new int[256];
        for (int i = 0; i < sims.length; i++) {
            init[sims[i]]++;
        }

        char[] strs = str.toCharArray();
        // 第一个滑动窗口
        for (int i = 0; i < sims.length; i++) {
            if (init[strs[i]]-- <= 0) {
                invalids++;
            }
        }
        for (int i = sims.length; i < strs.length; i++) {
            // 滑动窗口之前判断窗口是否已经匹配到同源异构字符
            if (invalids == 0) {
                return i - sim.length();
            }
            // 窗口右边增加的词
            if (init[strs[i]]-- <= 0) {
                invalids++;
            }
            // 窗口左边减少的词
            if (init[strs[i - sims.length]]++ < 0) {
                invalids--;
            }
        }
        return invalids == 0 ? strs.length - sims.length : -1;
    }

    public static void test(String str, String sim, int i) {
        System.out.println("******************");
        System.out.println(str);
        System.out.println(sim);
        if (i < 0) {
            System.out.println("not match");
        } else {
            System.out.println(str.substring(i, i + sim.length()));
        }
        System.out.println("******************");
    }
    public static void main(String[] args) {
        String str = "ckaabcszdf";
        String sim = "cbzs";
        int i = simstr(str, sim);
        test(str, sim, i);
    }
}
